% Profundidade de Uma Arvore
prof_arv(0,[]).
prof_arv(T,[N,_,_,N,_]) :-
	T is N + 1.
prof_arv(T,[E,_,_,D,_]) :-
	D > E, T is D + 1.
prof_arv(T,[E,_,_,D,_]) :-
	E > D, T is E + 1.


% Profundidade das sub-arvores
prof_sarv(E,D,[E,_,_,D,_]).


% Modulacao de uma Arvore
mod_arv([NE,E,T,ND,D],E,T,D) :-
	prof_arv(NE,E),
	prof_arv(ND,D).


% Verifica se a Necessidade de Rotacao
rota_arv(A,R) :-
	prof_sarv(NE,ND,A),
	NE -1 > ND,
	rotd_arv(A,R).
rota_arv(A,R) :-
	prof_sarv(NE,ND,A),
	ND -1 > NE,
	rote_arv(A,R).
rota_arv(A,A).


% Roda a Arvore
rotd_arv(A,R) :-
	mod_arv(A,E,T,D),
	prof_sarv(ENE,END,E),
	END > ENE,
	rote_arv(E,RE),
	mod_arv(RE,EE,ET,ED),
	mod_arv(X,ED,T,D),
	mod_arv(R,EE,ET,X).
rotd_arv(A,R) :-
	mod_arv(A,E,T,D),
	mod_arv(E,EE,ET,ED),
	mod_arv(X,ED,T,D),
	mod_arv(R,EE,ET,X).
rote_arv(A,R) :-
	mod_arv(A,E,T,D),
	prof_sarv(DNE,DND,D),
	DNE > DND,
	rotd_arv(D,RD),
	mod_arv(RD,DE,DT,DD),
	mod_arv(X,E,T,DE),
	mod_arv(R,X,DT,DD).
rote_arv(A,R) :-
	mod_arv(A,E,T,D),
	mod_arv(D,DE,DT,DD),
	mod_arv(X,E,T,DE),
	mod_arv(R,X,DT,DD).


% Insere um Elemento numa Arvore
avl_insert([],N,[0,[],N,0,[]]).
avl_insert([NE,E,N,ND,D],N,[NE,E,N,ND,D]). % Como pedido, se encontrar o elemento retorna true
avl_insert([_,E,T,_,D],N,R) :-
	N > T,
	avl_insert(D,N,RR),
	mod_arv(RRR,E,T,RR),
	rota_arv(RRR,R).
avl_insert([_,E,T,_,D],N,R) :-
	N < T,
	avl_insert(E,N,RR),
	mod_arv(RRR,RR,T,D),
	rota_arv(RRR,R).


% Remove um Elemento de uma Arvore
avl_remove([],_,[]). % Como pedido, se naum encontrar o elemento retorna true
avl_remove([_,[],N,_,D],N,D).
avl_remove([_,E,N,_,[]],N,E).
avl_remove([NE,E,N,ND,D],N,R) :-
	NE >= ND,
	rotd_arv([NE,E,N,ND,D],RR),
	avl_remove(RR,N,R).
avl_remove([NE,E,N,ND,D],N,R) :-
	ND > NE,
	rote_arv([NE,E,N,ND,D],RR),
	avl_remove(RR,N,R).
avl_remove([_,E,T,_,D],N,R) :-
	N > T,
	avl_remove(D,N,RR),
	mod_arv(RRR,E,T,RR),
	rota_arv(RRR,R).
avl_remove([_,E,T,_,D],N,R) :-
	N < T,
	avl_remove(E,N,RR),
	mod_arv(RRR,RR,T,D),
	rota_arv(RRR,R).


% Imprime um Arvore Deitada
print_arv([],_) :- nl.
print_arv([0,[],T,0,[]],N) :-
	tab(N),tab(N),
	write(T),nl.
print_arv([_,E,T,_,D],N) :-
	print_arv(E,N+1),
	tab(N),tab(N),
	write(T),nl,
	print_arv(D,N+1).


% Deleta uma Variavel
dvar(A) :-
	retract(var(A,_)).


% Salva a Arvore depois de uma insercao
saveins(A,N) :-
	var(A,ARV),
	avl_insert(ARV,N,R),
	retract(var(A,ARV)),
	assert(var(A,R)).
saveins(A,N) :-
	avl_insert([],N,R),
	assert(var(A,R)).


% Salva a Arvore depois de uma Remocao
saverem(A,N) :-
	var(A,ARV),
	avl_remove(ARV,N,R),
	retract(var(A,ARV)),
	assert(var(A,R)).


% Executa uma Lista de Comandos de insercao e remocao
exl_arv([]).
exl_arv([A|R]) :-
	A > 0,
	write(===),nl,
	saveins(exl,A),
	var(exl,X),
	nl,
	print_arv(X,0),
	exl_arv(R).
exl_arv([A|R]) :-
	A < 0,
	B is -A,
	write(---),nl,
	saverem(exl,B),
	var(exl,X),
	nl,
	print_arv(X,0),
	exl_arv(R).